package com.xigua._数学;

import java.util.TreeMap;

/**
 * 给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。

 注意：n 的值小于15000。

 */
public class _456_132模式 {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,-4,-3,-5,-1};
        System.out.println(find132pattern1(nums));
    }
    public static boolean find132pattern(int[] nums) {
        if (nums.length<3) return false;
        for (int i = 0; i < nums.length-2; i++) {
            for (int j = i+1; j < nums.length-1; j++) {
                for (int k = j+1; k < nums.length; k++) {
                    if (nums[i]<nums[j] && nums[i]<nums[k] && nums[j]>nums[k]) return true;
                }
            }
        }
        return false;
    }

    public static boolean find132pattern1(int[] nums) {
        int length = nums.length;
        if (length<3) return false;

        int leftMin = nums[0];

        TreeMap<Integer,Integer> allRight = new TreeMap<>();

        for (int i = 2; i < length; i++) {
            allRight.put(nums[i],allRight.getOrDefault(nums[i],0)+1);
        }

        for (int j = 1; j < length-1; j++) {
            if (leftMin<nums[j]){
                Integer right = allRight.ceilingKey(leftMin+1);
                if (right!=null && right <nums[j]){
                    return true;
                }
            }
            leftMin = Math.min(leftMin,nums[j]);
            allRight.put(nums[j+1],allRight.get(nums[j+1])-1);
            if (allRight.get(nums[j+1])==0){
                allRight.remove(nums[j+1]);
            }
        }
        return false;

    }
}
